package org.liaohailong.helloworld.find;

import java.util.List;


/**
 * Author: liaohailong
 * Time: 2021/11/8 10:27
 * Describe:
 */
public class BinarySearch {

    public static <T extends Number & Comparable<T>> int find(List<T> list,
                                                              int fromIndex, int toIndex, T target) {
        // out of bounds
        if (fromIndex < 0 || toIndex > list.size())
            return -1;

        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            T midVal = list.get(mid);

            int cmp = midVal.compareTo(target);

            if (cmp < 0) {
                low = mid + 1;
            } else if (cmp > 0) {
                high = mid - 1;
            } else
                return mid; // key found
        }

        return -(low + 1); // key not found
    }
}
